package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2386. 找出数组的第 K 大和
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/21 18:53
 */
public class KSum {

    public static void main(String[] args) {
        KSum test = new KSum();

        // 2
//        int[] arr = {2, 4, -2};
//        int k = 5;

        // 10
//        int[] arr = {1, -2, 3, 4, -10, 12};
//        int k = 16;

        //
//        int[] arr = Utils.getArr(10000, -1000000000, 1000000000);
//        int k = 2000;
//        System.out.println(k);
//        System.out.println();

        int[] arr = Utils.getArr("C:\\lw\\myword\\test.txt");
        int k = 2000;

        long sum = test.kSum(arr, k);
        System.out.println(sum);
    }

    public long kSum(int[] nums, int k) {
        int length = nums.length;
        long sum = 0;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (num < 0) {
                nums[i] = -num;
            } else {
                sum += num;
            }
        }
        Arrays.sort(nums);
        PriorityQueue<Long> queue = new PriorityQueue<>((a, b) -> Long.compare(b, a));
        queue.add(0L);
        Long[] items = new Long[k];
        int limit = Math.min(length, k);
        for (int i = 0; i < limit; i++) {
            int size = queue.size();
            int num = nums[i];
            if (size == k && queue.peek() < num) {
                break;
            }
            queue.toArray(items);
            Arrays.sort(items, 0, size);
            for (int j = 0; j < size; j++) {
                long l = items[j] + num;
                System.out.println(l);
                if (queue.size() < k) {
                    queue.add(l);
                    continue;
                }
                if (queue.peek() <= l) {
                    break;
                }
                queue.poll();
                queue.add(l);
            }
        }
        return sum - queue.poll();
    }

}
